import java.util.Arrays;

/**
 * 插值查找
 * 不同于线性查找，二分查找必须是有序数组
 *
 * @Author: wanqian
 * @Date: 2021/2/3 13:57
 */
public class InsertSearch {

    public static int[] arr = {53, 3, 542, 748, 14, 214, 23, 77, 4, 5, 118, 45, 96, 1};

    public static void main(String[] args) {
        //需要对数组进行排序
        Arrays.sort(arr);
        System.out.println(String.format("排序后数组为： %s", Arrays.toString(arr)));
        int target = 14;
//        int i = binarySearch(arr, 0, arr.length - 1, target);
        int i = insertSearch(arr, 0, arr.length - 1, target);

        if (i != -1) {
            System.out.println(String.format("找到目标arr[%d] = %d", i, target));
        } else {
            System.out.println("未找到目标");
        }
    }

    /**
     * @param arr
     * @param left
     * @param right
     * @param target
     * @return
     */
    public static int insertSearch(int[] arr, int left, int right, int target) {

        //当递归到最后只剩一个数时，仍不是我们的目标数
        //下次递归则left > right，结束查找
        if (left > right) {
            return -1;
        }
        if (target < arr[left] || target > arr[right]) {
            return -1;
        }

        System.out.println("查找数组" + left + "到" + right);
        int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
        System.out.println("arr[" + mid + "] = " + arr[mid] );
        if (arr[mid] > target) {
            //中间值大于目标值，继续找左半边
            return insertSearch(arr, left, mid - 1, target);
        } else if (arr[mid] < target) {
            //中间值小于目标值，继续找右半边
            return insertSearch(arr, mid + 1, right, target);
        } else {
            //等于则直接结束查找，返回结果
            return mid;
        }

    }
}
